package stack_queue;

/**
 * @program: play-structure
 * @description: 循环队列
 * @author: baichen
 **/
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front;
    private int tail;
    private int size;           //元素个数

    //定义数组容积capacity
    public LoopQueue(int capacity) {
        //循环数组中有意识的浪费一个空间,所以这里要+1，相应的getCapacity方法那里要-1
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    //循环队列中最多装载的元素数量，要注意有一个空间要浪费的，即队头和队尾最多缺少一个元素的距离
    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int getSize() {
        return size;
    }

    //循环队列入队,front不变，tail+1，因为是循环队列，所以要跟data.length取余
    @Override
    public void enqueue(E e) {

        if ((tail + 1) % data.length == front) {   //判断队列是否“满”，队满则扩容
            resize(getCapacity() * 2);        //队列扩容,循环队列最多存放的元素的2倍
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    private void resize(int newCapacity) {
        //因为浪费一个空间，所以要加一
        E[] newData = (E[]) new Object[newCapacity + 1];
//        遍历方式一，toString中是另一种便利方式
        for (int i = 0; i < size; i++) {
            //将data中的size个元素放到了newData中的[0，size-1]的位置
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    //循环队列出队，tail不变，front+1,因为是循环队列，所以要跟data.length取余
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty");
        }
        E ret = data[front];
        data[front] = null;     //清空队首
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    //取得队首元素
    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public String toString(){		//打印输出

        StringBuilder res = new StringBuilder();
        res.append(String.format("LoopQueue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");		//队列左侧是队首
        //循环地+1，所以要(i + 1) % data.length；第二种遍历方式，resize里面是另一种遍历方式
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)	//判断当前索引不是最后一个元素，既不是队尾
                res.append(", ");
        }
        res.append("] tail");		//队列右侧是队尾
        return res.toString();
    }

    public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<>();	//添加测试用例
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);		//将0-9这10个数字存放到 queue 中
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();	//每隔三个数字执行出队操作
                System.out.println(queue);
            }
        }
    }
}
